package com.fanshuai.algorithms.greedy;

/**
 * 0-1背包问题无法使用贪心算法，因为0-1背包有空隙。
 * 如果背包允许装入部分物品，则可以用贪心算法：将物品按价格重量比(v[i]/w[i])降序排序，然后从前往后依次装入背包，
 * 装不满的物品只装入一部分，填满背包
 */
public class Bag {
    /**
     * 部分背包问题
     * @param w
     * @param v
     * @param W
     * @return
     */
    public static double knapsack(double[] w, double[] v, double W) {
        //按性价比排序
        sort(w, v, 0, w.length - 1);

        double curW = W;
        double maxV = 0;
        int j = 0; //加入集合的当前索引
        while (curW >= w[j]) {
            maxV += v[j];
            curW -= w[j];
            j++;
        }

        if (curW > 0 && j < w.length) { //加入部分物品
            maxV += curW / w[j] * v[j];
        }
        return maxV;
    }

    //快排
    private static void sort(double[] w, double[] v, int start, int end) {
        if (start >= end) {
            return;
        }

        int partition = partition(w, v, start, end);
        sort(w, v, start, partition - 1);
        sort(w, v, partition + 1, end);
    }

    private static int partition(double[] w, double[] v, int start, int end) {
        int i = start - 1, j = end;
        while (i <= j) {
            while (compare(w, v, ++i, end) < 0 && i < end) ;
            while (compare(w, v, --j, end) > 0 && j > start);

            if (i >= j) {
                break;
            }
            swap(w, v, i, j);
        }

        swap(w, v, i, end);
        return i;
    }

    private static void swap(double[] w, double[] v, int i, int j) {
        double d = w[i];
        w[i] = w[j];
        w[j] = d;

        d = v[i];
        v[i] = v[j];
        v[j] = d;
    }

    //降序排列
    private static int compare(double[] w, double[] v, int i, int j) {
        if (v[i] == 0) {
            return -1;
        }
        if (v[j] == 0) {
            return 1;
        }

        double valuei = v[i] / w[i];
        double valuej = v[j] / w[j];
        return Double.compare(valuej, valuei);
    }

    public static void main(String[] args) {
        double[] w = {1, 2, 3, 4, 10};
        double[] v = {20, 11, 22, 100, 100};

        System.out.println(knapsack(w, v, 12));
    }


}
